package com.fanqi.nxplayer;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by fanqi on 2020/5/18.
 * Description:
 * HashMap+双向链表
 * <p>
 * HashMap<key,Node></key,Node>
 * Node里面存储 key value
 */
public class LRUCache {

    private class Node {

        public Node pre;
        public Node next;
        public int key;
        public int value;

        Node(int key, int val) {
            this.key = key;
            this.value = val;
        }
    }

    private Node head;
    private Node end;
    private int maxCapacity;
    private Map<Integer, Node> map = new HashMap<>();

    public LRUCache(int capacity) {
        this.maxCapacity = capacity;
    }

    public synchronized int get(int key) {
        //其实真正的存值在node里面
        Node node = map.get(key);
        if (node != null) {
            //注意一点，get时，相当于访问了数据，所以这里面应该将此node节点转移到node head
            refreshNode(node);
            return node.value;
        }
        return -1;
    }

    private void refreshNode(Node node) {
        if (node == head) {
            return;
        }
        //将该节点从原来的双向链表中断开，然后还需要判断此节点是否有前驱后继
        remove(node);
        //将该节点转移到链表的头节点
        addAppendToHead(node);
    }

    private void addAppendToHead(Node node) {
        if (head == null) {
            head = end = node;
        } else {
            node.next = head;
            head.pre = node;
            head = node;
        }
    }

    private void remove(Node node) {
        //如果头节点和尾节点相等，那直接删除
        if (head == end) {
            head = end = null;
        } else {
            //如果删除的是头节点
            if (head == node) {
                head = node.next;
                node.next = null;
            } else if (node == end) {
                end = node.pre;
                node.pre = null;
                node.next = null;
            } else {
                //断开连接，让链表中的数据重新指向新的连接节点
                node.pre.next = node.next;
                node.next.pre = node.pre;

                node.pre = null;
                node.next = null;
            }
        }
    }

    public synchronized void put(int key, int value) {

        //先看有没有这个key，无则直接插入，有则更新
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            refreshNode(node);
        } else {
            node = new Node(key, value);
            //判断map当前size是否小与最大限制？大于则删除老久不使用的，然后插入头部。小于的话，则直接插入头部。
            if (map.size() >= maxCapacity) {
                //删旧的
                map.remove(end.key);
                remove(end);
                addAppendToHead(node);
                map.put(key, node);
            } else {
                //直接插入
                addAppendToHead(node);
                map.put(key, node);
            }
        }

    }
}
